//
//  YKNode.c
//  ProjectM
//
//  Created by gaofeng on 2021/4/17.
//
#include <stdlib.h>
#include "YKNode.h"
//void vistNode(YKNode cd, YKNode nd);
void vistNode(YKNode *cd, YKNode *nd);

YKList creatList(void){
/**使用以下方法申明结构会遇到问题
 * 在当前函数结束，结构体变量会被回收，因为是系统分配的内存，想要长期保存需要使用malloc手动分配
 * YKNode n0,n1,n2,n3;
 */
//    推荐使用方式
    YKList L = malloc(sizeof(YKNode));
    L->data=0;
    L->next = NULL;
    return  L;
}
void headInsert(YKList lh,int data){
    YKNode *nd = malloc(sizeof(YKNode));
    nd->data = data;
    nd->next=lh->next;
    lh->next = nd;
    lh->data++;
}
void trailInsert(YKList lh,int data){
    YKNode *nd = malloc(sizeof(YKNode));
    nd->data = data;
    nd->next = NULL;
    YKNode *n1 = lh;
    for (int i=0; i<lh->data; i++) {
        n1 = n1->next;
    }
    n1->next = nd;
    lh->data++;
    
}
// 倒插法 带头节点
YKList creatListe(int a[],int len){
//    int a[5] ={1,2,3,4,5};
    YKList ll = malloc(sizeof(YKNode));
    YKNode *nd;
    for (int i = 0 ; i < len;  i++) {
        nd = malloc(sizeof(YKNode));
        nd->data = a[i];
        nd->next =  ll->next;
        ll->next = nd;
    }
    ll->data = len;
    return  ll;
}
YKList creatListHeadNode(int a[],int len){
    YKList lh = malloc(sizeof(YKNode));
    lh->data = len;
    YKNode *nd ,*cd=lh;
    for (int i = 0 ; i<len ; i++) {
        nd = malloc(sizeof(YKNode));
        nd->data = a[i];
        nd->next = NULL;
        cd->next = nd;
        cd = nd ;
    }
    return  lh;
}

// 头插法 不带头节点
YKList creatListb(int a[],int len){
    YKList ll = malloc(sizeof(YKNode));
    YKNode *nd, *rd = ll;
    rd->data = a[0];
    for (int i = 1 ; i < len;  i++) {
        nd = malloc(sizeof(YKNode));
        nd->data = a[i];
        rd->next = nd;
        rd = nd ;
    }
    rd->next = NULL;
    return  ll;
}


void printList(YKList L){
    YKNode *ll = L->next;
    while (ll != NULL) {
        printf("%d ",ll->data);
        ll = ll->next;
    }
    printf("\n");
}
void printNodes(YKNode nd){
    while (nd.data != 0) {
        printf("%d ",nd.data);
        nd = *nd.next;
    }
    printf("\n");
}
int  deletNode(YKList L,int data){
    YKNode *pn = L;
    YKNode *cn = L->next;
    while (cn) {
        if (cn->data == data) {
            pn->next = cn->next;
            free(cn);
            L->data--;
            return  1;
        }
        pn = cn;
        cn = cn->next;
    }
    return  0;
}
YKList deletElemte(YKList lt,int ele){
    YKNode *na = lt;
    YKNode *nn = na->next;
// YKNode *nn = lt->next;
    while (nn) {
        if (nn->data == ele) {
            na->next = nn->next;
            free(nn);
        }
        na = nn;
        nn = nn->next;
    }
    // 判断第一个节点
    na = lt;
    if (na->data == ele) {
        lt = na->next;
        free(na);
    }
    
    return  lt;
}
void deletElemtea(YKList *lt,int ele){
    YKNode *na = *lt;
    if (na==NULL) {
        return;
    }
    if (na->data==ele) {
        *lt = na->next;
        free(na);
    }
    deletElemtea(&(na->next), ele);
}
// 不会断链，存在二级指针，二级指针应该会记录节点信息
void deletElemteb(YKList *lt,int ele){
    YKNode *p;
    if (*lt == NULL) {
        return;
    }
    if ((*lt)->data == ele) {
        p = *lt;
        *lt = (*lt)->next;
        free(p);
        deletElemteb(lt, ele);
    }else{
        deletElemteb(&(*lt)->next, ele);
    }
}
// 会断链
void deletElemtec(YKNode *lt,int ele){
    YKNode *p ;
    if (lt == NULL) {
        return;
    }
    if (lt->data == ele) {
        p=lt;
        lt = lt->next;
        free(p);
        deletElemtec(lt,ele);
    }else{
        deletElemtec(lt->next, ele);
    }
}
void deletElemHeadList(YKList lh,int ele){
    YKNode *cd = lh;
    YKNode *nd = lh->next;
    while (nd) {
        if (nd->data==ele) {
            cd->next = nd->next;
            free(nd);
            nd = cd->next;
            lh->data--;
        }else{
            cd = nd;
            nd = cd->next;
        }
    }
    return;
}
// 并没有释放
YKList deletElemHeadListA (YKList lh,int ele){
    YKNode *pd = lh->next, *rd = lh, *qd;
    while (pd) {
        if (pd->data != ele) {
            rd->next = pd;
            rd = pd;
            pd = pd->next;
        }else{
            qd = pd;
            pd = pd->next;
            free(qd);
            lh->data--;
        }
//        pd = pd->next;
    }
    rd->next =NULL;
    return  lh;
}
YKList overturnList(YKList lt){
    // 借助数组实现链表翻转，空间复杂度为n
    YKNode *nl[20];
    int i = 0;
    while (lt) {
        nl[i] = lt;
        lt = lt->next;
        i++;
    }
    YKNode *na = nl[0];
    na->next = NULL;
    lt = nl[i-1];
    for (int j=i-1; j>0; j--) {
        YKNode *nt = nl[j];
        nt->next = nl[j-1];
    }
    return  lt;
}
YKList overturnListB(YKList lt) {
    YKNode* p = lt->next;
    lt->next = NULL;
    YKNode* q = p->next;
    //p->next = NULL;
    while (p)
    {
        p->next = lt;
        lt = p;
        p = q;
        if (p) //最后p=q=null，是不能执行 p->next
        {
            q = p->next;
        }
     
    }
 /*   p->next = lt;
    lt = p;*/
    //printf("%d ", p->data);
    return lt;
}
void deletElemted(YKNode lt,int ele){
    
}
void test0(void){
    int a[5] = {1,2,3,4,5};
    YKList ll =  creatListb(a,5);
    YKNode *n1 = ll->next;
    YKNode n2 = *(n1->next);
    printf("%d \n",n2.data);
}
int nodeMain(void){
    return  1;
}
